package org.dlx.common;

public class KMP
{
    private char[] _search;
    private char[] _pattern;
    private int[] _next;
    public KMP(char[] s, char[] p) {
        _search = s;
        _pattern = p;
        _next = new int[_pattern.length];
        buildNext();
    }

    int find(){
        int i = 0;
        int j = 0;
        int slen = _search.length;
        int plen = _pattern.length;
        while(i < slen && j < plen) {
            //字符匹配成功则前进 或者首位字符匹配失败也是前进
            if(j == -1 || _search[i] == _pattern[j]) {
                i++;
                j++;
            }
            else{
                j = _next[j];
            }
        }
        if(j == plen)
            return i - j;
        else
            return -1;
    }

    private void buildNext(){
        int plength = _pattern.length;
        int i = 0;
        int j = -1;//i==0时当前_next值 != 0时上一次_next值
        _next[0] = -1;//首字符 -1
        while(i < plength) {
            if(j == -1 || _pattern[i] == _pattern[j]){
                i++;
                j++;
                _next[i] = j;//如果相等代表公共字串的长度+1
                //优化
//                if(_pattern[i] != _pattern[j]) {
//                    _next[i] = j;
//                }else{
//                    _next[i] = _next[j];
//                }
            }else
                j = _next[j];//如果不等则迭代
        }
    }
}
